package algorithms.question.class04;

import common.util.MyUtil;

/**
 * leetcode 53
 * 返回一个数组中，子数组最大累加和
 *
 * @author guichang
 * @date 2021/7/31
 */

@SuppressWarnings("all")
public class Code2_子数组最大累加和 {

    public static void main(String[] args) {
        int[] nums = MyUtil.createRandomArray(10, -10, 10);
        //int[] nums = MyUtil.createArray(-4, -6, 1, 2, 10, 6, -6, 9, 10, -7);
        MyUtil.print(maxSubArray(nums));
    }

    public static int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return Integer.MIN_VALUE;
        }
        int N = nums.length;
        // 0-i的子数组必须以i结尾的子数组最大累加和为help[i]
        int[] help = new int[N];
        help[0] = nums[0];
        for (int i = 1; i < N; i++) {
            int p1 = nums[i];// 仅以i位置结尾
            int p2 = nums[i] + help[i - 1];// i位置往左扩
            help[i] = Math.max(p1, p2);
        }
        // 0~i的子数组的累加和最大为dp[i]
        int[] dp = new int[N];
        dp[0] = Math.max(0, help[0]);
        for (int i = 1; i < N; i++) {
            int p1 = dp[i - 1]; // 不以i结尾
            int p2 = help[i]; // 必须以i结尾
            dp[i] = Math.max(p1, p2);
        }
        return dp[N - 1];
    }
}